package code.mySpecializedTraining;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/14
 * @description
 */
public class BackTrace {
    // 77. 组合
    public List<List<Integer>> combine(int n, int k) {
        // [1,2,3,4,...,n] 选k个，无重复元素，不能重复选，顺序无关，返回所有组合
        List<List<Integer>> lists = new ArrayList<>();
        combineBT(1, 0, n, k, new ArrayList<>(), lists);
        return lists;
    }

    private void combineBT(int nowPos, int count, int n, int k, List<Integer> list, List<List<Integer>> lists) {
        if (count == k) {
            lists.add(new ArrayList<>(list));
            return;
        }
        // 剪枝(可选)：如果剩下的元素全选，也已经不够k-count了，则直接返回吧
        if (n - nowPos + 1 < k - count)
            return;
        for (int i = nowPos; i <= n; i++) {
            list.add(i);
            combineBT(i + 1, count + 1, n, k, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 216. 组合总和 III
    public List<List<Integer>> combinationSum3(int k, int n) {
        // [1,2,...,9] 选k个，和为n，无重复元素，不可重复选，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        combinationSum3BT(1, 0, 0, n, k, new ArrayList<>(), lists);
        return lists;
    }

    private void combinationSum3BT(int nowPos, int count, int sum, int n, int k, List<Integer> list, List<List<Integer>> lists) {
        if (count == k && sum == n) {
            lists.add(new ArrayList<>(list));
            return;
        }
        // 剪枝:和大于了直接结束吧
        if (sum > n)
            return;
        for (int i = nowPos; i <= 9; i++) {
            list.add(i);
            combinationSum3BT(i + 1, count + 1, sum + i, n, k, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 17. 电话号码的字母组合
    public List<String> letterCombinations(String digits) {
        Map<Character, char[]> map = new HashMap<>();
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
        List<String> stringList = new ArrayList<>();
        letterCombinationsBT(0, digits, new StringBuilder(), stringList, map);
        return stringList;
    }

    private void letterCombinationsBT(int pos, String digits, StringBuilder sb, List<String> stringList, Map<Character, char[]> map) {
        if (pos == digits.length()) {
            String s = sb.toString();
            if (!s.isEmpty())
                stringList.add(s);
            return;
        }
        char c = digits.charAt(pos);
        for (int i = 0; i < map.get(c).length; i++) {
            sb.append(map.get(c)[i]);
            letterCombinationsBT(pos + 1, digits, sb, stringList, map);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    // 39. 组合总和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 无重复元素，可重复使用，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        combinationSumBT(0, candidates, target, new ArrayList<>(), lists);
        return lists;
    }

    private void combinationSumBT(int startPos, int[] candidates, int target, List<Integer> list, List<List<Integer>> lists) {
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        if (target < 0)
            return;
        for (int i = startPos; i < candidates.length; i++) {
            list.add(candidates[i]);
            combinationSumBT(i, candidates, target - candidates[i], list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 40. 组合总和 II
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 有重复元素（相同元素在答案比较中算一个），不能重复使用，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        // 这种情况下先排序
        Arrays.sort(candidates);
        combinationSum2BT(0, target, candidates, new ArrayList<>(), lists);
        return lists;
    }

    private void combinationSum2BT(int startPos, int target, int[] candidates, List<Integer> list, List<List<Integer>> lists) {
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        if (target < 0)
            return;
        for (int i = startPos; i < candidates.length; i++) {
            // 同样的数字只递归遍历第一个
            if (i != startPos && candidates[i] == candidates[i - 1])
                continue;
            list.add(candidates[i]);
            combinationSum2BT(i + 1, target - candidates[i], candidates, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 131. 分割回文串
    public List<List<String>> partition(String s) {
        List<List<String>> lists = new ArrayList<>();
        partitionBT(0, s, new ArrayList<>(), lists);
        return lists;
    }

    private void partitionBT(int left, String s, List<String> list, List<List<String>> lists) {
        if (left == s.length()) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int right = left; right < s.length(); right++) {
            if (!isHW(s, left, right))
                continue;
            list.add(s.substring(left, right + 1));
            partitionBT(right + 1, s, list, lists);
            list.remove(list.size() - 1);
        }
    }

    private boolean isHW(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }

    // 93. 复原 IP 地址
    public List<String> restoreIpAddresses(String s) {
        List<String> stringList = new ArrayList<>();
        restoreIpAddressesBT(0, s, new ArrayList<>(), stringList);
        return stringList;
    }

    private void restoreIpAddressesBT(int startPos, String s, List<Integer> list, List<String> stringList) {
        if (list.size() == 4 && startPos == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (int num : list) {
                sb.append(num);
                sb.append(".");
            }
            sb.deleteCharAt(sb.length() - 1);
            stringList.add(sb.toString());
            return;
        }
        if (list.size() == 4)
            return;
        for (int endPos = startPos; endPos < s.length(); endPos++) {
            // 大于3位的情况，排除；大于1位且第一个数字是0的排除
            if (endPos - startPos >= 3 || endPos - startPos >= 1 && s.charAt(startPos) == '0')
                continue;
            // 三位且大于255的排除
            int num = Integer.parseInt(s.substring(startPos, endPos + 1));
            if (num > 255)
                continue;
            list.add(num);
            restoreIpAddressesBT(endPos + 1, s, list, stringList);
            list.remove(list.size() - 1);
        }
    }

    // 78. 子集
    public List<List<Integer>> subsets(int[] nums) {
        // 无重复元素，不可重复选，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        subsetsBT(0, nums, new ArrayList<>(), lists);
        return lists;
    }

    private void subsetsBT(int startPos, int[] nums, List<Integer> list, List<List<Integer>> lists) {
        lists.add(new ArrayList<>(list));
        for (int i = startPos; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsBT(i + 1, nums, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 90. 子集 II
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 有重复元素（相同元素在答案比较中算一个），不可重复选，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        // 先排序
        Arrays.sort(nums);
        subsetsWithDupBT(0, nums, new ArrayList<>(), lists);
        return lists;
    }

    private void subsetsWithDupBT(int startPos, int[] nums, List<Integer> list, List<List<Integer>> lists) {
        lists.add(new ArrayList<>(list));
        for (int i = startPos; i < nums.length; i++) {
            if (i != startPos && nums[i] == nums[i - 1])
                continue;
            list.add(nums[i]);
            subsetsWithDupBT(i + 1, nums, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 491. 非递减子序列
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 有重复元素，不可重复选，顺序无关
        List<List<Integer>> lists = new ArrayList<>();
        findSubsequencesBT(0, nums, new ArrayList<>(), lists);
        return lists;
    }

    private void findSubsequencesBT(int startPos, int[] nums, List<Integer> list, List<List<Integer>> lists) {
        if (list.size() >= 2)
            lists.add(new ArrayList<>(list));
        // 与 40. 组合总和 II 和 78. 子集 不同的原因是：这道题不让排序，相同元素可能不在一起！
        Set<Integer> set = new HashSet<>();
        for (int i = startPos; i < nums.length; i++) {
            if (set.contains(nums[i]))
                continue;
            set.add(nums[i]);
            if (!list.isEmpty() && list.get(list.size() - 1) > nums[i])
                continue;
            list.add(nums[i]);
            findSubsequencesBT(i + 1, nums, list, lists);
            list.remove(list.size() - 1);
        }
    }

    // 46. 全排列
    public List<List<Integer>> permute(int[] nums) {
        // 无重复元素，不可重复选，顺序相关
        List<List<Integer>> lists = new ArrayList<>();
        permuteBT(nums, new ArrayList<>(), lists, new boolean[nums.length]);
        return lists;
    }

    private void permuteBT(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] isVisited) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isVisited[i])
                continue;
            isVisited[i] = true;
            list.add(nums[i]);
            permuteBT(nums, list, lists, isVisited);
            list.remove(list.size() - 1);
            isVisited[i] = false;
        }
    }

    // 47. 全排列 II
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 有重复元素，不可重复选，顺序相关
        List<List<Integer>> lists = new ArrayList<>();
        // 先排序
        Arrays.sort(nums);
        permuteUniqueBT(nums, new ArrayList<>(), lists, new boolean[nums.length]);
        return lists;
    }

    private void permuteUniqueBT(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] isVisited) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isVisited[i])
                continue;
            // 相同元素，只有前一个被访问过，才能访问下一个
            if (i != 0 && nums[i] == nums[i - 1] && !isVisited[i - 1])
                continue;
            isVisited[i] = true;
            list.add(nums[i]);
            permuteUniqueBT(nums, list, lists, isVisited);
            list.remove(list.size() - 1);
            isVisited[i] = false;
        }
    }

    // 51. N 皇后
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> lists = new ArrayList<>();
        char[][] chess = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(chess[i], '.');
        }
        solveNQueensBT(n, 0, chess, new HashSet<>(), new HashSet<>(), new HashSet<>(), lists);
        return lists;
    }

    private void solveNQueensBT(int n, int row, char[][] chess, Set<Integer> column, Set<Integer> LUpRDown, Set<Integer> RUpLDown, List<List<String>> lists) {
        if (row == n) {
            // 当前为一个答案
            List<String> stringList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(chess[i][j]);
                }
                stringList.add(sb.toString());
            }
            lists.add(stringList);
            return;
        }
        // 遍历这行的所有位置
        for (int col = 0; col < n; col++) {
            // 如果这个位置能被同列其他元素攻击，换下一个
            if (column.contains(col))
                continue;
            // 如果这个位置能被斜着的"\"线攻击，换下一个
            if (RUpLDown.contains(row - col))
                continue;
            // 如果这个位置能被写着的"/"线攻击，换下一个
            if (LUpRDown.contains(row + col))
                continue;

            column.add(col);
            RUpLDown.add(row - col);
            LUpRDown.add(row + col);
            chess[row][col] = 'Q';
            solveNQueensBT(n, row + 1, chess, column, LUpRDown, RUpLDown, lists);
            chess[row][col] = '.';
            LUpRDown.remove(row + col);
            RUpLDown.remove(row - col);
            column.remove(col);
        }
    }

    // 37. 解数独
    private boolean isFinished = false;

    public void solveSudoku(char[][] board) {
        // 约束
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][] area = new boolean[9][10];
        // 找到9x9盘中所有要递归遍历的点
        List<int[]> poses = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    poses.add(new int[]{i, j});
                else {
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    area[i / 3 + 3 * (j / 3)][num] = true;
                }
            }
        }
        solveSudokuBT(0, poses, board, row, col, area);
    }

    private void solveSudokuBT(int pos, List<int[]> poses, char[][] board, boolean[][] row, boolean[][] col, boolean[][] area) {
        if (pos == poses.size()) {
            isFinished = true;
            return;
        }
        // 遍历当前pos填1-9的情况
        int x = poses.get(pos)[0];
        int y = poses.get(pos)[1];
        for (int num = 1; num <= 9; num++) {
            // 如果当前填不了i，continue
            if (row[x][num] || col[y][num] || area[x / 3 + 3 * (y / 3)][num])
                continue;
            // 可以填i
            row[x][num] = true;
            col[y][num] = true;
            area[x / 3 + 3 * (y / 3)][num] = true;
            board[x][y] = (char) ('0' + num);
            solveSudokuBT(pos + 1, poses, board, row, col, area);
            // 如果 isFinished 说明结束了
            if (isFinished)
                break;
            board[x][y] = '.';
            row[x][num] = false;
            col[y][num] = false;
            area[x / 3 + 3 * (y / 3)][num] = false;
        }
    }

    // 241. ※为运算表达式设计优先级
    public List<Integer> diffWaysToCompute(String expression) {
        int len = expression.length();
        List<Integer> list = new ArrayList<>();
        // 看这个 expression 是否没有运算符
        int firstOp = 0;
        while (firstOp < len) {
            if (Character.isDigit(expression.charAt(firstOp))) {
                firstOp++;
                continue;
            }
            break;
        }
        if (firstOp == len) {
            list.add(Integer.parseInt(expression));
            return list;
        }
        // 分治法，选定一个运算符，左右递归
        for (int i = 0; i < len; i++) {
            if (Character.isDigit(expression.charAt(i)))
                continue;
            List<Integer> left = diffWaysToCompute(expression.substring(0, i));
            List<Integer> right = diffWaysToCompute(expression.substring(i + 1, len));
            // 搞到所有结果
            for (int x : left) {
                for (int y : right) {
                    switch (expression.charAt(i)) {
                        case '+' -> list.add(x + y);
                        case '-' -> list.add(x - y);
                        case '*' -> list.add(x * y);
                    }
                }
            }
        }
        return list;
    }

    // 526. 优美的排列（还有DP解法）
    private int ans526 = 0;
    public int countArrangement(int n) {
        countBackTrace(0, n, new boolean[n + 1]);
        return ans526;
    }

    private void countBackTrace(int count, int n, boolean[] visited) {
        if (count == n) {
            ans526++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (visited[i])
                continue;
            if (i % (count + 1) == 0 || (count + 1) % i == 0) {
                visited[i] = true;
                countBackTrace(count + 1, n, visited);
                visited[i] = false;
            }
        }
    }


    // 473. 火柴拼正方形（还有状态DP解法）
    public boolean makesquare(int[] matchsticks) {
        // 1 <= matchsticks.length <= 15
        int sumLen = Arrays.stream(matchsticks).sum();
        // 递减顺序排序，先选大的边，可以有效剪枝
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }
        // 总长度
        if (sumLen % 4 != 0)
            return false;
        int l = sumLen / 4;
        // 回溯
        return backTrace473(matchsticks, 0, new int[4], l);
    }

    private boolean backTrace473(int[] m, int index, int[] edges, int l) {
        if (index == m.length)
            return true;
        for (int i = 0; i < edges.length; i++) {
            edges[i] += m[index];
            if (edges[i] <= l && backTrace473(m, index + 1, edges, l))
                return true;
            edges[i] -= m[index];
        }
        return false;
    }
}
